We study the structure of automata accepting the greedy representations of N in awide class of numeration systems. We describe the conditions under which such automata canhave more than one strongly connected component and the form of any such additional components. Our characterization applies, in particular, to any automaton arising from a Bertrandnumeration system. Furthermore, we show that for any automaton A arising from a systemwith a dominant root > 1, there is a morphism mapping A onto the automaton arising fromthe Bertrand system associated with the number . Under some mild assumptions, we alsostudy the state complexity of the trim minimal automaton accepting the greedy representationsof the multiples of m>=2 for a wide class of linear numeration systems. As an example, thenumber of states of the trim minimal automaton accepting the greedy representations of mN inthe Fibonacci system is exactly 2m^2.
展开▼
